package com.heima.algorithm.recursion_multi;

/**
 * <h2>杨辉三角形</h2>
 * <h2>1 &nbsp;</h2>
 * <h2>1 &nbsp; 1</h2>
 * <h2>1 &nbsp; 2 &nbsp; 1</h2>
 * <h2>1 &nbsp; 3 &nbsp; 3 &nbsp; 1</h2>
 * <h2>1 &nbsp; 4 &nbsp; 6 &nbsp; 4 &nbsp; 1</h2>
 */
public class PascalTriangle {

    /**
     * 对外界提供的打印杨辉三角函数
     *
     * @param n 杨辉三角的高度
     */
    public static void printPascalTriangle1(int n) {
        for (int i = 0; i < n; i++) {
            printSpace(i, n);
            for (int j = 0; j <= i; j++) {
                System.out.printf("%-4d", element1(i, j));
            }
            System.out.println();
        }
    }

    /**
     * 对外界提供的打印杨辉三角函数，用记忆法优化，用的二维数组
     *
     * @param n 高度
     */
    public static void printPascalTriangle2(int n) {
        int[][] triangle = new int[n][];
        for (int i = 0; i < n; i++) {
            triangle[i] = new int[i + 1];
            printSpace(i, n);
            for (int j = 0; j <= i; j++) {
                System.out.printf("%-4d", element2(i, j, triangle));
            }
            System.out.println();
        }
    }

    /**
     * <h3>动态规划</h3>
     * 对外界提供的打印杨辉三角函数，用记忆法优化，但是用的一维数组，而且没有用到递归
     * @param n 高度
     */
    public static void printPascalTriangle3(int n) {
        int[] triangle = new int[n];
        for (int i = 0; i < n; i++) {
            createRow(triangle, i);
            printSpace(i, n);
            for (int j = 0; j <= i; j++) {
                System.out.printf("%-4d", triangle[j]);
            }
            System.out.println();
        }
    }

    /**
     * 根据索引位置查找元素，时间复杂度为O(2^i)，相当于以（i，j）为根节点，两边扩散成为二叉树，深度为i，规模增大，深度会加深，为指数级规模
     *
     * @param i i
     * @param j j
     * @return 找到的元素
     */
    private static int element1(int i, int j) {
        if (j == 0 || i == j) {
            return 1;
        }
        return element1(i - 1, j - 1) + element1(i - 1, j);
    }

    /**
     * 根据索引位置查找元素，时间复杂度为O(n^2)，递归的时候去掉了重复的递归，相当于进行一次不重复的遍历，1 + 2 + 3 + …… + n = ……
     *
     * @param i        i
     * @param j        j
     * @param triangle 存放杨辉三角指定位置的值的二维数组
     * @return 元素值
     */
    private static int element2(int i, int j, int[][] triangle) {
        if (triangle[i][j] > 0) {
            return triangle[i][j];
        }
        if (j == 0 || i == j) {
            triangle[i][j] = 1;
            return 1;
        }
        triangle[i][j] = element2(i - 1, j - 1, triangle) + element2(i - 1, j, triangle);
        return triangle[i][j];
    }

    /**
     * 打印索引第i行的空格
     *
     * @param i    索引i
     * @param high 杨辉三角的高度
     */
    private static void printSpace(int i, int high) {
        for (int j = 0; j < (high - i - 1) * 2; j++) {
            System.out.print(" ");
        }
    }

    /**
     * 在原数组基础（上一行）上改出第索引i行的一维数组，存放的是i行的元素
     * @param row 存放数据的一维数组
     * @param i 第i行
     */
    private static void createRow(int[] row, int i) {
        if (i == 0) {
            row[i] = 1;
        }
        for (int j = i; j > 0; j--) {
            row[j] = row[j] + row[j - 1];
        }
    }
}
